Step 2: Setup for Dijkstra's

Before we start the algorithm, we need to initialize our helper data structures.

Guidance for Step 2

  • `dist` array: Stores the shortest distance from `S` to `i`. What should the default value be? (Hint: A number larger than any possible path).
  • `parent` array: Stores the path. `parent[i] = k` means we reached `i` *from* `k`. This is essential for finding the "next hop".
  • Priority Queue (`pq`): A min-heap to store `(cost, node)` tuples. This lets us always visit the closest node next.
  • Initialize Source: The distance to the source `S` is 0. Push `(0, S)` to the `pq` to start. 
import heapq

# 1. Distance array
#    Initialize all distances to infinity
dist = [ float('______') ] * V

# 2. Parent array (for tracking the path)
#    Initialize all parents to -1 (or another invalid node)
parent = [ ______ ] * V

# 3. Priority Queue (min-heap)
pq = []

# 4. Initialize the source node
#    The distance to S from S is 0
dist[S] = ______

# Push the starting point onto the heap
# The heap stores (cost, node_id)
heapq.heappush(pq, (______, ______))
Copied!